The present invention relates to associative memories and in particular memories of the  less than  less than TRIE greater than  greater than  type (derived from the English verb  less than  less than reTRIEve greater than  greater than ).
The principle of the  less than  less than TRIE greater than  greater than  memory was proposed by R. de la Briandais and E. Fredkin et al towards the end of the 1950s (see E. Fredkin et al.:  less than  less than Trie Memory greater than  greater than , Communications of the ACM, Vol. 3, No. 9, September 1960, pages 490-499). It consists in cutting up the bit strings to be recognised into successive slices of a fixed length (of K bits) and integrating them in a two-dimensional table T. Each row of the table constitutes a register of 2K elementary cells. A register (R) is assigned to each slice of the string and a cell in the register is associated with the value (V), ranging between 0 and 2Kxe2x88x921 of this slice. The contents (C=T[R,V]) of the cell determined in this manner represent either the register allocated to the subsequent slice (or pointer) or an end of analysis reference (or  less than  less than status greater than  greater than ) if the analysis of the string must end on this slice.
The register allocated to the first slice of the string, which is also the point of entry to the table, is also referred to as the portal register. The data to be analysed in the form of bit strings, i.e. to be compared with the contents of the TRIE memory, will also be referred to as routes hereafter. The term path will be used to denote the succession of stringed cells in the table associated with a route. Each register of the table will be said to be of order ixe2x89xa70 if it is attributed to the (i+1)-th slice of one or more stored routes. The portal register will therefore be of order 0. The TRIE memory associates with each of its registers of order ixe2x89xa70 a unique sequence of iK bits corresponding to the iK first bits of each route whose path in the table passes via a cell of the register in question.
The following example will provide an illustration of how data is stored in a TRIE memory in the specific case where K=4. The value of each slice is represented by a digit in hexadecimal numbering (0,1, . . . E,F) and each of the registers contains 24=16 cells.
Let us assume that the routes to be recognised are those commencing with the patterns 45A4, 45AB, 67AB, 788A and 788BD, to which the statuses S0, S1, S2, S3 and S0 have been allocated respectively (a same status may be shared by several routes). By using the row index for the register R and the column index for the value V of the slices and by taking the register R0=0 as the portal register, the table of the TRIE memory will appear as illustrated in FIG. 1, the underlined data being the statuses. The codes 45A4, 45AB, 67AB, 788A and 788BD are represented respectively in the table of FIG. 1 by the paths:
T[0,4]xe2x86x92T[1,5]xe2x86x92T[2,A]xe2x86x92T[3,4];
T[0,4]xe2x86x92T[1,5]xe2x86x92T[2,A]xe2x86x92T[3,B];
T[0,6]xe2x86x92T[4,7]xe2x86x92T[5,A]xe2x86x92T[6,B];
T[0,7]xe2x86x92T[7,8]xe2x86x92T[8,8]xe2x86x92T[9,A];
T[0,7]xe2x86x92T[7,8]xe2x86x92T[8,8]xe2x86x92T[9,B]xe2x86x92T[10,D].
From this example, it may be seen that all the codes starting with a common part of iK bits are represented by common a initial path in the memory, leading to the register of order i with which the sequence formed by these iK bits is associated.
If we consider a route to be analysed, cut up into a series of binary slices of values Vi where 0xe2x89xa6ixe2x89xa6N and {Ri} is the series of registers associated with the values Vi, where R0 still denotes the portal register, the analysis algorithm implemented may be that illustrated in FIG. 2.
On initialisation 1 of this algorithm, the rank of analysis i is set to 0 and the portal register R0 is selected as the register R. In each iteration of rank i, the contents C of the cell T[R,Vi], denoted by the (i+1)-th slice Vi of the route in the register of order i selected, is read at step 2. If this cell contains a continue analysis pointer, which will indicate at test 3 the value 1 for a bit FP(C) stored in the cell, the register of order i+1 denoted by this pointer Ptr(C) is selected as the register R for the next iteration at step 4 and the rank i is incremented. If test 3 reveals a cell which does not contain a pointer (FP(C)=0), the status Ref(C) read in the cell concerned is returned at step 5 as a result of looking up the table.
This algorithm enables routes containing any number of slices to be analysed. A same table may be used for several types of analysis, by organising the data on the basis of different portal registers. Furthermore, it enables the analysis time of the data to be controlled: analysing a number N of slices of K bits will require at most N times the duration of one iteration.
The algorithm of FIG. 2 may be implemented very rapidly by a hardware component controlling the accesses to the memory array. In particular, it will enable high-performance routers to be set up for packet-switched telecommunications networks. The header of the packets is analysed by the component on the fly and the status associated with a route designates, for example, an output port of the router to which the packets bearing a destination address conforming to this route must be routed.
Such a router may be a multi-protocol router. This being the case, the different sections of the header are analysed on the basis of different portal registers. For example, a first analysis of a header field (or several) indicating the protocol used and/or the version of this protocol may be analysed from a first portal register. This first analysis will provide a reference which, although corresponding to a logical end of the analysis, may be incorporated in the TRIE memory by a continue analysis pointer denoting another portal register to be used for analysing the rest of the header. The reference in question may also trigger time delays or skips by a given number of bits in the header being analysed in order to be able to choose which portion of the header should be analysed next. In practice, a certain number of analyses are generally run in succession in order to trigger the operations required by the protocols supported, depending on the content of the headers. One of these analyses will relate to the destination addressed needed to complete the routing function strictly speaking.
A router of the type outlined above is described in French patent 2 707 775. On the subject of using a TRIE memory in routers, reference may be made to the article  less than  less than Putting Routing Tables in Silicon greater than  greater than  by T. B. Pei et al., IEEE Network Magazine, January 1992, pages 42-50.
The Internet Protocol (IP) is one of the communication protocols which may be supported by the router.
The IP routing process is essentially based on analysing the destination addresses of level 3 of the protocol (see C. Huitxc3xa9ma:  less than  less than Le Routage dans I""Internet greater than  greater than , Editions Eyrolles, 1995). The addresses of the frames to be routed are inscribed in an internal management table, called a routing table or  less than  less than forwarding table greater than  greater than , where they are associated with parameters which characterise the accesses to which they are directed. In its broad lines, the routing operation consists in comparing the addresses carried by the incoming frames with those contained in the table and directing them to the correct interface.
Most of the addresses are declared in what is referred to as an aggregate form. An aggregate describes a set of addresses by means of the data in a common header and a mask which sets the bit length of the part of the address to be analysed. This presentation of the data in the table is very much linked to the way in which addresses are assigned, associating an aggregate to a sub-network or a set of sub-networks and hence implicitly a geographical location. These aggregates may contain specific details for some of their addresses which require a specific routing.
For example, if representing the addresses in hexadecimal format, the data to be stored in a routing table may of the type:
4A0, mask 10xe2x86x92Port P1;
4A2, mask 12xe2x86x92Port P2;
4A28, mask 14xe2x86x92Port P3.
This gives an orientation code for the addresses analysed, prefixed by the underlined binary patterns below:
0100 1010 00XX, etc., direct to port P1,
0100 1010 0010 XXXX, etc. direct to port P2,
0100 1010 0010 10XX, etc. direct to port P3.
This specification provided by the longest patterns is known under the name of  less than  less than longest match greater than  greater than  management. It is known that this management complicates the routers used significantly (see the articles:  less than  less than Routing on Longest-Matching Prefixes greater than  greater than , by W. Doeringer et al., IEEE/ACM Trans. on Networking, Vol. 4, No. 1, February 1996, pages 86-97;  less than  less than Small Routing Tables for Fast Routing Lookups greater than  greater than  by M. Degermark et al., Proc. of the SIGCOMM"" 97 Conference, Cannes, France, 1997, pages 3-14;  less than  less than Scalable High Speed Routing Lookups greater than  greater than , by M. Waldvogel et al., Proc. of the SIGCOMM"" 97 Conference, Cannes, France, 1997, pages 25-36.
A priori, the TRIE memory is well suited to the routing table function in an IP frame routing process. The concept of pattern is equated with the concept of an address to be recognised and the status may carry the information needed to direct the data.
However, the algorithms used to keep the contents of the TRIE memory up to date do not satisfactorily meet the constraints imposed by the  less than  less than longest match greater than  greater than  management. For example, inserting both a status S0 which is valid for the pattern V0, . . . VN, and another status S1 which is valid for the longer pattern V0, . . . VN,VN+1, . . . ,VP in the TRIE table is critical. Furthermore, these algorithms generally assume that the binary data to be analysed is of a length. which is a multiple of the size K of slices, which is not the case when managing an IP routing table whose masks may of be of any length.
One object of the invention is to overcome the practical limitations encountered with TRIE memories and in particular to enhance the possibilities offered by routers using these memories.
Accordingly, the invention proposes a method of updating an associative memory of the TRIE type organised in the form of a set of registers of 2K cells having at least one portal register from which bit strings are analysed in successive slices of K bits, K being an integer at least equal to 1. Each non-empty cell of the TRIE memory contains data incorporating either a continue analysis pointer or a reference. The TRIE memory associates an integer order ixe2x89xa70 and a respective sequence of iK bits with each register. The analysis of a bit string consists of at least one iteration of rank i, starting from the rank i=0 for which the portal register of order 0 is selected, whereby the iteration of rank i comprises the steps of:
reading data in a cell of the register of order i selected, denoted by the (i+1)-th slice of K bits in the string analysed;
if the data read contains a continue analysis pointer, selecting a register of order i+1 of the TRIE memory as indicated by said pointer, the sequence associated with the register of order i+1 selected being formed by the first (i+1)K bits of the string analysed, then running the iteration of rank i+1;
if the data read represents end analysis data and contains no continue analysis pointer, terminating the analysis by issuing a reference contained in said end analysis data.
According to the invention, the data are stored in the cells of the TRIE memory in response to commands to insert and delete binary patterns of variable length each associated with a reference, so that when a bit string is being analysed, the reference issued will be that associated with the longest of the binary patterns matching the start of the string analysed.
Two auxiliary tables may also be used for updating purposes: a mirror table which reflects the contents of the TRIE memory and a ghost table storing the references associated with the binary patterns inserted.
The mirror table is made up of registers of 2K cells, each corresponding to a respective register of the TRIE memory allocated to the portal register. Each of the 2K cells of a register in the mirror table then corresponds to a respective cell in the corresponding register of the TRIE memory. Each cell in the mirror table corresponding to a non-empty cell of a register of order ixe2x89xa70 of the TRIE memory contains at least:
information indicating whether the corresponding cell of the TRIE memory contains a continue analysis pointer;
if the corresponding cell of the TRIE memory contains a continue analysis pointer, the continue analysis pointer in question;
if the corresponding cell of the TRIE memory does not contain a continue analysis pointer but a reference, the length of a binary pattern associated with this reference;
and, preferably, information indicating whether the corresponding cell in the TRIE memory is ghosted, i.e. whether, for at least one integer depth D such that 0xe2x89xa6D less than K, a pattern of (i+1)Kxe2x88x92D bits has been inserted, the first iK bits of which form the sequence associated with said register of order i and the last Kxe2x88x92D bits of which correspond to the first Kxe2x88x92D of the K bits denoting said corresponding cell of the TRIE memory within said register of order i.
For each ghosted cell of a register of order ixe2x89xa70 in the TRIE memory, the ghost table stores each reference associated with an inserted pattern of (i+1)Kxe2x88x92D bits, such that 0xe2x89xa6D less than K, the first iK bits of which form the sequence associated with said register of order i and the last Kxe2x88x92D bits of which correspond to the first Kxe2x88x92D of the K bits denoting said ghosted cell of the TRIE memory within said register of order i.
To respond to a command to insert a first pattern of L=MK+B bits associated with a first reference, where M and B are integers such that Mxe2x89xa70 and 1xe2x89xa6Bxe2x89xa6K, it is of advantage to run the following operations:
selecting the portal register of order 0;
if M greater than 0, proceeding with the following steps /a/ to /e/ for each of the values of the rank i increasing from 0 to Mxe2x88x921:
/a/ reading the data in a first cell of the mirror table corresponding to the cell of the TRIE memory indicated by the (i+1)-th slice of K bits of the first pattern within the register of order i selected;
/b/ if the data read in the first cell indicates that the corresponding cell of the TRIE memory contains a continue analysis pointer, selecting the register of the TRIE memory designated by said pointer as the register of order i+1;
/c/ if the data read in the first cell indicates that the corresponding cell of the TRIE memory does not contain a continue analysis pointer, selecting a register available in the TRIE memory as a register of order i+1, writing in the corresponding cell of the TRIE memory a continue analysis pointer designating the selected register of order i+1 and writing in the first cell of the mirror table an indication that the corresponding cell of the TRIE memory contains a continue analysis pointer as well as said pointer;
/d/ if a second reference, associated with a second binary pattern, was previously obtained, writing said second reference in each non-ghosted cell of the TRIE memory belonging to the register of order i selected and not containing a pointer and write the length of said second binary pattern in each corresponding cell of the mirror table;
/e/ if the data read in the first cell indicates that the corresponding cell of the TRIE memory is ghosted, obtaining from the ghost table a second reference associated with a second binary pattern constituted by the inserted pattern of (i+1)Kxe2x88x92D bits having a minimum depth D, the first iK bits of which form the sequence associated with the register of order i selected and the last Kxe2x88x92D bits of which correspond to the first Kxe2x88x92D bits of the K bits denoting said ghosted cell within the register of order i selected;
proceeding with the following steps /f/ to /j/ for each slice of K bits of the form 2Kxe2x88x92BVM+Z where VM is the number formed by the last B bits of the first pattern and Z is an integer ranging between 0 and 2Kxe2x88x92Bxe2x88x921:
/f/ reading data in a second cell of the mirror table corresponding to the cell of the TRIE memory denoted by said slice 2Kxe2x88x92BVM+Z within the register of order M selected;
/g/ if the data read in the second cell indicates that the corresponding cell of the TRIE memory is ghosted, obtaining from the ghost table the length of the inserted pattern of (M+1)Kxe2x88x92D bits having a minimum depth D, the first MK bits of which form the sequence associated with the register of order M selected and the last Kxe2x88x92D bits of which correspond to the first Kxe2x88x92D bits of the K bits designating said ghosted cell within the register of order M selected and do not run steps /h/ to /j/ if the depth obtained is less than Kxe2x88x92B;
/h/ if the data read in the second cell indicates that the corresponding cell of the TRIE memory is not ghosted, writing in the second cell of the mirror table an indication that the corresponding cell of the TRIE memory is ghosted;
/i/ if the data read in the second cell indicates that the corresponding cell of the TRIE memory contains a continue analysis pointer, recursively propagating the first reference associated with the first binary pattern starting from the register designated by said continue analysis pointer;
/j/ if the data read in the second cell indicates that the corresponding cell of the TRIE memory does not contain a continue analysis pointer, writing said first reference in said corresponding cell of the TRIE memory and write the length of said first binary pattern in the second cell of the mirror table;
writing in the ghost table the first reference, in relation with the depth Kxe2x88x92B for each cell of the TRIE memory designated by a slice of K bits of the form 2Kxe2x88x92BVM+Z, where Z is an integer ranging between 0 and 2Kxe2x88x92Bxe2x88x921; and
running step /d/ for the rank i=M.
Furthermore, in order to respond to a command to delete a first pattern of L=MK+B bits associated with a first reference, where M and B are integers such that Mxe2x89xa70 and 1xe2x89xa6Bxe2x89xa6K, it is advantageous to run a recursive procedure, starting from rank i=0 for which the portal register of order 0 is selected, whereby said recursive procedure comprises nested iterations for the ranks ixe2x89xa70 and each iteration of rank ixe2x89xa70 comprises the operations of:
if i less than M, proceeding with the following steps /axe2x80x2/ to /hxe2x80x2/:
/axe2x80x2/ selecting for the rank i a first cell of the mirror table corresponding to the cell of the TRIE memory denoted by the (i+1)-th slice of K bits of the first pattern within the register of order i selected and reading data in the first cell selected for rank i;
/bxe2x80x2/ if the data read in the first cell selected for rank i indicates that the corresponding cell of the TRIE memory is ghosted, obtaining from the ghost table a second reference associated with a second binary pattern constituted by the inserted pattern of (i+1)Kxe2x88x92D bits having a minimum depth D, the first iK bits of which form the sequence associated with the register of order i selected and the last Kxe2x88x92D bits of which correspond to the first Kxe2x88x92D bits of the K bits denoting said ghosted cell within the register of order i selected;
/cxe2x80x2/ selecting as a register of order i+1 a register of the TRIE memory designated by a continue analysis pointer included in the data read;
/dxe2x80x2/ performing the iteration of rank i+1;
/exe2x80x2/ writing in the first cell of the mirror table selected for the rank i an indication that the corresponding cell of the TRIE memory does not contain a continue analysis pointer;
/f/ if a second reference associated with a second binary pattern was previously obtained, writing said second reference in the cell of the TRIE memory corresponding to the first cell selected for rank i and write the length of said second binary pattern in the first cell selected for rank i;
/gxe2x80x2/ if no second reference was previously obtained, writing in the first cell selected for rank i an indication that the corresponding cell of the TRIE memory is empty;
/hxe2x80x2/ if i greater than 0 and each cell of the register of the mirror table corresponding to the register of order i selected indicates that the corresponding cell of the TRIE memory does not contain a continue analysis pointer and is not ghosted, making the register of order i selected available;
if i=M, deleting the reference associated with the first binary pattern of the ghost memory for the cell of the TRIE memory denoted by the slice of K bits 2Kxe2x88x92BVM from the register of order M selected for the rank M where VM is the number formed by the last B bits of the first pattern and proceed with the following steps /ixe2x80x2/ to /Ixe2x80x2/ for each cell of the TRIE memory designated by a slice of K bits of the form 2Kxe2x88x92BVM+Z, where Z is an integer ranging between 0 and 2Kxe2x88x92Bxe2x88x921:
/ixe2x80x2/ looking up the ghost table to determine whether it contains, for said cell denoted by the slice 2Kxe2x88x92BVM+Z, at least one reference associated with a third binary pattern of a depth at least equal to Kxe2x88x92B and, as applicable, selecting the third binary pattern of minimum depth;
/jxe2x80x2/ if the ghost table does not contain a reference for said cell denoted by the slice 2Kxe2x88x92BVM+Z, writing in the corresponding cell of the mirror table an indication that said cell denoted by the slice 2Kxe2x88x92BVM+Z is not ghosted and, if a second reference associated with a second binary pattern was previously obtained, selecting said second binary pattern as the third binary pattern;
/kxe2x80x2/ if a third binary pattern has been selected and if said cell designated by the slice 2Kxe2x88x92BVM+Z contains a continue analysis pointer according to the data read in the corresponding cell of the mirror memory, recursively propagating a third reference associated with the selected third binary pattern starting from the register designated by said continue analysis pointer, taking account of the length of the first binary pattern;
/Ixe2x80x2/ if a third binary pattern has been selected and if said cell designated by the slice 2Kxe2x88x92BVM+Z does not contain a continue analysis pointer according to the data read in the corresponding cell of the mirror memory, writing in the cell of the TRIE memory denoted by said slice 2Kxe2x88x92BVM+Z a third reference associated with the third binary pattern selected and writing the length of the selected third binary pattern in the corresponding cell of the mirror table.
Another aspect of the present invention relates to a packet processing device such as a packet router, having circuitry for analysing the header of packets received, using an associative memory of the TRIE type, and means for updating the TRIE memory operating in accordance with a method such as that defined above.